package com.sheng.leetcode.year2022.swordfingeroffer.day28;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/09/26
 *<p>
 * 剑指 Offer 37. 序列化二叉树<p>
 *<p>
 * 请实现两个函数，分别用来序列化和反序列化二叉树。<p>
 * 你需要设计一个算法来实现二叉树的序列化与反序列化。<p>
 * 这里不限定你的序列 / 反序列化算法执行逻辑，<p>
 * 你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。<p>
 * 提示：输入输出格式与 LeetCode 目前使用的方式一致，<p>
 * 详情请参阅LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。<p>
 *<p>
 * 示例：<p>
 * 输入：root = [1,2,3,null,null,4,5]<p>
 * 输出：[1,2,3,null,null,4,5]<p>
 *<p>
 * 注意：本题与主站 297 题相同：<a href="https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/">...</a><p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0037 {

    @Test
    public void test01() {
        Codec codec = new Codec();
//        TreeNode root = new TreeNode(1);
//        TreeNode right = new TreeNode(3);
//        TreeNode rightleft = new TreeNode(4);
//        rightleft.left = new TreeNode(6);
//        rightleft.right = new TreeNode(7);
//        right.left = rightleft;
//        right.right = new TreeNode(5);
//        root.left = new TreeNode(2);
//        root.right = right;
        TreeNode root = new TreeNode(1);
        String serialize = codec.serialize(root);
        System.out.println(serialize);
        TreeNode node = codec.deserialize(serialize);
        System.out.println(node);
    }
}
class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        // root为空时，直接返回空字符串
        if (root == null) {
            return "";
        }
        StringBuilder str = new StringBuilder();
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        // 通过层序遍历的方式对二叉树进行序列化
        serializeBFS(list, str);
        return str.toString();
    }

    public void serializeBFS(List<TreeNode> list, StringBuilder str) {
        boolean flag = false;
        List<TreeNode> nodes = new ArrayList<>();
        // 循环二叉树的每个子节点
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) != null) {
                // 子节点不为null时
                str.append(list.get(i).val);
            } else {
                // 子结点为null时
                str.append("null");
            }
            if (i != list.size() - 1) {
                // 每一个子节点之间通过 / 进行分割
                str.append("/");
            } else {
                // 每一层之间通过 # 进行分割
                str.append("#");
            }
            // 判断当前结点是否为 null
            if (list.get(i) != null) {
                // 判断左子节点是否为 null
                if (list.get(i).left != null) {
                    // 不为空时，将flag置为true
                    nodes.add(list.get(i).left);
                    flag = true;
                } else {
                    nodes.add(null);
                }
                if (list.get(i).right != null) {
                    nodes.add(list.get(i).right);
                    flag = true;
                } else {
                    nodes.add(null);
                }
            }
        }
        // 集合中存在一个元素不为null，即代表存在子节点不为null，继续遍历下一层
        if (flag) {
            serializeBFS(nodes, str);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        // 空字符串代表二叉树为null
        if ("".equals(data)) {
            return null;
        }
        // 获取每一层的结点的序列化组成一个字符串数组
        String[] split = data.split("#");
        // 第一个为根结点
        TreeNode root = new TreeNode(Integer.parseInt(split[0]));
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        // 遍历
        deserializeBFS(list, split, 1);
        return root;
    }

    public void deserializeBFS(List<TreeNode> list, String[] split, int index) {
        // 如果index 长度大于等于数组长度，返回
        if (index >= split.length) {
            return;
        }
        // n代表每一层的非空子树的左结点的序号
        int n = 0;
        // 获取当前层的每一个子节点
        String[] strings = split[index].split("/");
        List<TreeNode> nodes = new ArrayList<>();
        for (TreeNode node : list) {
            // 如果当前结点为空则跳过
            if (node != null) {
                // 不为空，则判断 n子树的两个元素是否为null，不为null则将其元素放入当前结点的左右结点中
                if (!"null".equals(strings[n])) {
                    node.left = new TreeNode(Integer.parseInt(strings[n]));
                }
                if (!"null".equals(strings[n + 1])) {
                    node.right = new TreeNode(Integer.parseInt(strings[n + 1]));
                }
                // n往后一个子树，即往后移动两个结点
                n += 2;
                // 将当前结点的左右子树放入集合中
                nodes.add(node.left);
                nodes.add(node.right);
            }
        }
        // 如果 index 长度没有到达二叉树的最后一层则继续遍历
        if (split.length - 1 != index) {
            deserializeBFS(nodes, split, index + 1);
        }
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
